An RS codeword is composed of N J-bit symbols of which K represents information and the remaining N-K symbols represent check symbols. Each check symbol is a linear combination of a distant subset of information symbols. RS codes have the following parameters:
______________________________________ J number of bits comprising each RS symbol N = 2.sup.J - 1 number of symbols per RS codeword E symbol correction capability per RS codeword 2E number of checks symbols K = N - 2E number of symbols representing information I the depth of symbol interleaving ______________________________________
Parameters J, E and I are independent. Each of the 2E check symbols (computed by an RS encoder) is a linear combination of a distinct subset of the K symbols representing information. Hence (N,K) RS codes are linear. Furthermore, every cyclic permutation of the symbols of an RS codeword results in a codeword.
The class of cyclic codes is a proper subset of the class of linear codes. Cyclic codes have a well defined mathematical structure. Encoders and decoders of cyclic codes are implementable by means of feedback shift registers (FSRs). However, RS codes are nonbinary and each stage must be capable of assuming each of the 2.sup.J state-values corresponding to representations of J-bit symbols. Consequently, solid-state random-access memories (RAMs) are commonly used to serve as nonbinary FSR stages in RS encoders and decoders.
Every pair of distinct codewords belonging to a (N,K) RS code differs in at least 2E+1 corresponding symbols. The code thus has a minimum Hamming distance of 2E+1 and is E symbol error-correcting. A symbol is in error if one or more bits comprising the symbol are in error. A received word with any combination of E or fewer symbols in error will be correctly decoded. Whereas a received word containing more than E erroneous symbols will be incorrectly decoded with a probability of less than 1 chance in E factorial (i.e., 1/E!). Such a received word will be declared to be uncorrectable during the decoding process with probability 1-(1/E!).
Erroneous symbols (of a received word) confined to a region of E or fewer contiguous symbols in bit serial form are correctable. In terms of bits, every single burst-error (contained within a received word) of length J(E-1)+1 bits or less affects at most E symbols and thus is correctable.
A concatenated (NI,KI) RS code resulting from symbol interleaving to a depth of I is comprised of KI consecutive information symbols over which 2EI check symbols are computed and appended such that every I.sup.th symbol, starting with symbol 1,2, . . . or I, belongs to the same (N,K) RS codeword. If a received word of a (NI,KI) code contains any single burst-error of length J(EI-1)+1 bits, the number of erroneous symbols belonging to the same N-symbol word will not exceed E. Upon symbol deinterleaving, each of the I, N-symbol words will be correctly decoded. Thus symbol interleaving to a depth of I increases the length (in bits) of correctable burst-errors by over I-fold.
It is the burst-error correction capability of RS codes that is exploited in concatenated coding where a convolution (probabilistic) code is the inner code and an RS (algebraic) code serves as the outer code. A large number of bit-errors within a burst results in a relatively few number of symbol errors. Convolutional codes outperform algebraic codes over a Gaussian channel. Burst-errors are encountered in a low signal-to-noise ratio environment. Also, in such an environment, a Viterbi decoder (of a convolutional code) can lose bit or symbol synchronization. This results in the generation of bursts by the Viterbi decoder. Until synchronization is re-established, burst-error protection is provided by the outer RS code. Expectation of burst-lengths among other factors (such as information rate K/N, a measure of efficiency, and transfer frame length in packet telemetry) influence the choice of magnitudes of parameters E and I. The effect of an infinite symbol interleaving depth can be achieved with a small value of I.
Mathematical Characterization of RS Symbols
A codeword of a (N,K) RS code is represented by a vector of N symbols (i.e., components) EQU C.sub.N-1 C.sub.N-2. . . C.sub.2E C.sub.2E-1. . . C.sub.0 ( 1)
where C.sub.i is taken from a finite field 2.sup.J elements. The finite field is known as a Galois Field of order 2.sup.J or simply GF(2.sup.J). Each element in GF(2.sup.J) is a distinct root of EQU x.sup.2.spsp.J -x=x(x.sup.2.spsp.J.sbsp.-1 -1)=0 (2)
The element O satisfies x=0 and each of the nonzero elements satisfies EQU x.sup.2.spsp.J.sbsp.-1 -1=0 (3)
The nonzero roots of unity in Equation (3) form a "multiplicative group" which is cyclic and of order N=2.sup.J -1. The "multiplicative" order of a root, .alpha., of Equation (3) is the least positive integer m for which EQU .alpha..sup.m =1 where 2.sup.J -1.tbd.0 mod m (4)
Note that m.vertline.2.sup.J -1 where u.vertline.v denotes u divides v. A root of maximum order (i.e., for which m=2.sup.J -1) is termed "primitive" and is a "generator" of the cyclic multiplicative group in GF(2.sup.J).
An irreducible (i.e., unfactorable) polynomial over a finite field is analogous to a prime integer. A fundamental property of Galois fields is that every irreducible polynomial F(x) of degree r over GF(2) where r.vertline.J (excluding x the only irreducible polynomial over GF(2) without a nonzero constant term) is a factor of EQU x.sup.2.spsp.J.sbsp.-1 -1
Though F(x) is unfactorable over the binary field (i.e., GF(2)), it contains r distinct roots in GF(2.sup.J). GF(2.sup.J) is a finite field extension of GF(2), whereas GF(2) is a proper subfield of GF(2.sup.J). GF(2.sup.s) is a proper subfield of GF(2.sup.J) if and only if s.vertline.J and s&lt;J.